#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "pathlist.h"

#define PATH_ALLOC 20

static int search (pathlist_t *pathlist, const char *path, size_t len, unsigned int *position);
static int allocate (pathlist_t *pathlist);

void pathlist_init (pathlist_t *pathlist)
{
	pathlist->records = NULL;
	pathlist->index = NULL;

	pathlist->size = 0;
	pathlist->used = 0;
}

void pathlist_free (pathlist_t *pathlist)
{
	if (pathlist->records) {
		free (pathlist->records);
		pathlist->records = NULL;
	}

	if (pathlist->index) {
		free (pathlist->index);
		pathlist->index = NULL;
	}

	pathlist->size = 0;
	pathlist->used = 0;
}

int pathlist_load (pathlist_t *pathlist, configuration_t *conf)
{
	const char *path;
	size_t i;

	/* Free previous configuration. */
	pathlist_free (pathlist);

	/* For each path... */
	for (i = 0; ((path = configuration_get_child (conf, i, "ReverseProxy", "HandledRemotely", NULL)) != NULL); i++) {
		if (pathlist_insert (pathlist, path, strlen (path)) < 0) {
			fprintf (stderr, "Couldn't insert path: %s.\n", path);
		}
	}

	return 0;
}

int search (pathlist_t *pathlist, const char *path, size_t len, unsigned int *position)
{
	path_t *record;
	int i, j, pivot;
	int ret;

	i = 0;
	j = pathlist->used - 1;

	while (i <= j) {
		pivot = (i + j) / 2;
		record = &(pathlist->records[pathlist->index[pivot]]);

		ret = strncmp (path, record->path, len);
		if (ret < 0) {
			j = pivot - 1;
		} else if (ret == 0) {
			if (len < record->len) {
				j = pivot - 1;
			} else if (len == record->len) {
				*position = (unsigned int) pivot;
				return 0;
			} else {
				i = pivot + 1;
			}
		} else {
			i = pivot + 1;
		}
	}

	*position = (unsigned int) i;

	return -1;
}

int allocate (pathlist_t *pathlist)
{
	path_t *records;
	off_t *index;
	size_t size;

	if (pathlist->used == pathlist->size) {
		size = pathlist->size + PATH_ALLOC;
		index = (off_t *) malloc (size * sizeof (off_t));
		if (!index) {
			return -1;
		}

		records = (path_t *) realloc (pathlist->records, size * sizeof (path_t));
		if (!records) {
			free (index);
			return -1;
		}

		if (pathlist->index) {
			memcpy (index, pathlist->index, pathlist->used * sizeof (off_t));
			free (pathlist->index);
		}

		pathlist->records = records;
		pathlist->index = index;
		pathlist->size = size;
	}

	return 0;
}

int pathlist_insert (pathlist_t *pathlist, const char *path, size_t pathlen)
{
	path_t *record;
	unsigned int position;

	if ((*path != '/') || (pathlen >= PATH_MAX)) {
		return -1;
	}

	/* If not root directory... */
	if (pathlen > 1) {
		/* Remove trailing '/' (if present). */
		if (path[pathlen - 1] == '/') {
			pathlen--;
		}
	}

	if (search (pathlist, path, pathlen, &position) < 0) {
		if (allocate (pathlist) < 0) {
			return -1;
		}

		record = &(pathlist->records[pathlist->used]);

		memcpy (record->path, path, pathlen);
		record->path[pathlen] = 0;
		record->len = pathlen;

		if (position < pathlist->used) {
			memmove (&(pathlist->index[position + 1]), &(pathlist->index[position]), (pathlist->used - position) * sizeof (off_t));
		}

		pathlist->index[position] = pathlist->used++;
	}

	return 0;
}

int pathlist_exists (pathlist_t *pathlist, const char *path, size_t pathlen)
{
	unsigned int position;
	size_t len;
	const char *ptr;
	const char *end;

	/* If not root directory... */
	if (pathlen > 1) {
		/* Remove trailing '/' (if present). */
		if (path[pathlen - 1] == '/') {
			pathlen--;
		}
	}

	len = 1;
	ptr = path;
	end = path + pathlen;

	do {
		if (search (pathlist, path, len, &position) == 0) {
			return 1;
		}

		if (len == pathlen) {
			return 0;
		}

		for (++ptr; ptr < end; ptr++) {
			if (*ptr == '/') {
				break;
			}
		}

		len = ptr - path;
	} while (1);
}
